class Solution {
    public int minCut(String s) {
        // 创建dp表、初始化、填表、返回值
        int n = s.length();
        int[] dp = new int[n];
        // 存储子串是否回文信息
        boolean[][] bool = palindromeSubstring(n, s);

        // // 初始化dp数组
        // Arrays.fill(dp, Integer.MAX_VALUE);

        // for (int i = 0; i < n; i++) {
        //     // 判断[0,i]是否为回文串
        //     if (!bool[0][i]) {
        //         for (int j = 1; j <= i; j++) {
        //             // 判断[j,i]是否为回文串
        //             if (bool[j][i]) {
        //                 dp[i] = Math.min(dp[i], dp[j-1]+1);
        //             }
        //         }
        //     } else {
        //         dp[i] = 0;
        //     }
        // }


        for (int i = 0; i < n; i++) {
            // 判断[0,i]是否为回文串
            if (!bool[0][i]) {
                int min = Integer.MAX_VALUE;
                for (int j = 1; j <= i; j++) {
                    // 判断[j,i]是否为回文串
                    if (bool[j][i]) {
                        min = Math.min(min, dp[j-1]+1);
                    }
                }
                dp[i] = min;
            }
        }

        return dp[n-1];
    }


    private boolean[][] palindromeSubstring(int n, String s) {
        // 创建dp表、初始化、填表、返回值
        boolean[][] bool = new boolean[n][n];

        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j >= i; j--) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j || i+1 == j) {
                        bool[i][j] = true;
                    } else {
                        bool[i][j] = bool[i+1][j-1];
                    }
                }
            }
        }

        return bool;
    }
}